import java.util.HashSet;
import java.util.Set;

/**
 * Created by L.jp
 * Description:编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 *  输入：[1, 2, 3, 3, 2, 1]
 *  输出：[1, 2, 3]
 *
 *  进阶：
 *
 * 如果不得使用临时缓冲区，该怎么解决？
 * User: 86189
 * Date: 2022-02-11
 * Time: 17:14
 */
 class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }
public class Solution {
     //对于这种链表修改指向的题目，应该是先判断下一步情况，再修改指向
    public ListNode removeDuplicateNodes(ListNode head) {
//利用哈希表去重的特性，来判断是否重复节点，遍历链表，先将链表的节点值放入哈希表，再通过哈希表是否包含下一个节点值的判断来改变链表指向，如果不包含，那么就指向下一个节点，如果包含那么就让它指向下一个节点的下一个节点，即使有多个重复的，他也会不断搜索直到不重复为止
//         Set<Integer> set=new HashSet<>();
//         ListNode cur=head;//遍历链表
//         while(cur!=null && cur.next!=null){//防止空指针异常
//             set.add(cur.val);
//             if(set.contains(cur.next.val)){
//                 cur.next=cur.next.next;
//             }else{
//                 cur=cur.next;
//             }
//         }
//         return head;

        //法二：进阶，不使用临时缓冲区
        //使用双重循环，一重循环是遍历链表，二重是排除与当前前驱节点相同的节点
        ListNode cur=head;
        while(cur!=null){
            //定义一个用于判断的节点
            ListNode judge=cur;
            while(judge.next!=null){
                if(judge.next.val!=cur.val){   //利用下一个节点值是否跟当前前驱节点值相同来排除重复节点
                    judge=judge.next;
                }else{
                    judge.next=judge.next.next;
                }
            }
            //每一次内循环结束都可以排除与前驱节点相同的节点
            //再从前驱节点的下一个节点接着开始下一轮排除
            cur=cur.next;
        }
        return head;
    }
}
